package com.redstar.day01_lianbiaofanzhuan;

import java.util.Objects;

/**
 * 链表反转
 * 1->2->3->4->5
 * 反转之后为：
 * 5->4->3->2->1
 *
 * @author lihongxing
 * @date 2021/04/16 01:49
 */
public class Reverse {

    private static Node generate(){
        Node node5 = new Node(5,null);
        Node node4 = new Node(4,node5);
        Node node3 = new Node(3,node4);
        Node node2 = new Node(2,node3);
        Node node1 = new Node(1,node2);
        return node1;
    }


    /**方法一：循环*/
    private static Node method01(Node head) {
        Node curr = head,next;
        Node prev = null;
        while (curr != null) {
            next = curr.getNext();
            curr.setNext(prev);
            prev = curr;
            curr = next;
        }
        return prev;

    }


    /**
     * 方法二：递归
     */
    private static Node recursion(Node head) {
        //如果传入的节点本身是空或者是最后一个元素的时候，返回本身
        if (Objects.isNull(head) || Objects.isNull(head.getNext())) {
            return head;
        }
        //否则，继续向下遍历，直到找到最后一个节点，然后从最后两个节点开始反转
        Node result = recursion(head.getNext());
        // todo lihongxing
        head.getNext().setNext(head);
        head.setNext(null);
        return result;
    }


    public static void main(String[] args) {
        System.out.println(generate());
        System.out.println(method01(generate()));
        System.out.println(recursion(generate()));
    }







}
